1. Technical Field
The present invention relates generally to hash functions, and more particularly to improving the performance of hash tables.
2. Discussion of Related Art
A hash table or hash map is a data structure used for storing and accessing data in computer systems, which associates a given key with a given value. A hash function is used to transform the key into a hash value (also called a hash code or hash sum) that serves as an index to an array element (e.g., a hash bucket) in the hash table where the key's corresponding value is stored. The hash table thus helps to speed up table lookup or data comparison tasks, such as finding items in a database. Ideally, the hash function would map each key to a unique hash value, but this ideal is difficult to achieve in practice and generally most hash functions result in at least one collision, i.e., two or more keys are mapped to the same hash value. Any collision in a hash table increases the average cost of lookup operations, thereby degrading the performance of the hash table. In most applications, it is desirable to minimize collisions, e.g., by preventing their occurrence or by resolving collisions as they occur during the generation of a hash table, in order to improve performance of the hash table.